class Solution:
    def smallestDistancePair(self, nums: list, k: int) -> int:
        nums.sort()
        left = 0
        right = nums[-1] - nums[0]
        while left < right:
            mid = (left + right) // 2
            start = 0
            cnt = 0
            for i in range(len(nums)):
                while start < len(nums) and nums[i] - nums[start] > mid:
                    start += 1
                cnt += (i - start)
            if cnt < k:
                left = mid + 1
            else:
                right = mid

        return right
